#include<iostream>
#include<stdlib.h>
#include<cstdlib>
#include<ctime> 
using namespace std;

class solution{
    private:
    int len;
    int array[11];
    public:
        solution(){
            len = sizeof(array)/sizeof(array[0]);
        }
        ~solution(){
			free(this); 
        }
        
    void quickSort1(int* arr, int l, int r){//操作是直接在数组的物理地址上进行的也就是向上级递归反馈结果 
        if (l >= r){//递归出口，最小子问题时直接返回解决 
            return;      
        }
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j){//int arr[] = {3,1,4,6,7,8,34,123,1,4,5};
	        /*
			结论：这个写法打错特错了，这是我的惯性思维写的代码垃圾代码。
			原因：每一次while循环只会在i或者j指针上移动一位，这就会导致i,j最终的移动步长是一样的，也就是说：我们默认当走到中间的时候
			左边的所有的比pivot小，右边的所有的元素比pivot大，显然这是不符合实际的。
			正确的思想应该是在每一趟先找到左边比poivot大的，再去找比p右边ivot小的，然后交换两者的次序，将此次记作一次基本操作。
			最后再将pivot放入它最终的位置。也就是i=j的那个地方，此地方是pivot的最终归宿。 
			
			*/ 
			i++;//从pivot后面一位开始比较 
			while (arr[i] < pivot){
				i++;
			}
			while (arr[j] > pivot){
				j--;	
			}
			if(i < j){
				swap(arr[i],arr[j]);
			}
        }
        //将pivot放入最终位置 
		arr[l] = arr[j];
        arr[j] = pivot;
        
        quickSort1(arr, l, j-1);
        quickSort1(arr, j+1, r);
        return;
    }
    
    
    void quickSort3(int* arr, int l, int r){//操作是直接在数组的物理地址上进行的也就是向上级递归反馈结果 
        if (l >= r){//递归出口，最小子问题时直接返回解决 
            return;      
        }
        srand((unsigned)time(NULL));
       	int pivotPos = rand()%(r-l)+l;
       	swap(arr[l], arr[pivotPos]);
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j){//int arr[] = {3,1,4,6,7,8,34,123,1,4,5};
	        /*
			结论：这个写法打错特错了，这是我的惯性思维写的代码垃圾代码。
			原因：每一次while循环只会在i或者j指针上移动一位，这就会导致i,j最终的移动步长是一样的，也就是说：我们默认当走到中间的时候
			左边的所有的比pivot小，右边的所有的元素比pivot大，显然这是不符合实际的。
			正确的思想应该是在每一趟先找到左边比poivot大的，再去找比p右边ivot小的，然后交换两者的次序，将此次记作一次基本操作。
			最后再将pivot放入它最终的位置。也就是i=j的那个地方，此地方是pivot的最终归宿。 
			
			*/ 
			i++;//从pivot后面一位开始比较 
			while (arr[i] < pivot){
				i++;
			}
			while (arr[j] > pivot){
				j--;	
			}
			if(i < j){
				swap(arr[i],arr[j]);
			}
        }
        //将pivot放入最终位置 ，与j(向前挪动的)交换次序 
		arr[l] = arr[j];
        arr[j] = pivot;
        
        quickSort3(arr, l, j-1);
        quickSort3(arr, j+1, r);
        return;
    }
    
    
    
    

    public: void swap(int& a1, int& a2){//必须通过引用或者指针交换值，否则函数内存释放后不会改变原来对象的值 
        int temp = a2;
        a2 = a1;
        a1 = temp;
    };

    void printArray(int arr[], int len){
        
        for (int i = 0; i < len; i++){
                cout << arr[i]<<" ";
        }
        cout<<endl;
    }

};


int main()
{
  int arr[] = {3,1,4,6,7,8,34,123,1,4,5};
  int *p1 = arr;
  int len = sizeof(arr)/sizeof(arr[0]);//数组作为形式参数都会被视为指针，所以现在调用函数的外部计算数组长度 
  
  solution* s1 = new solution();
  s1->quickSort1(p1, 0, len-1);
  s1->printArray(arr,len);
  int j = 0;
  cout<<"test:"<<endl;
  cout<<j++<<"先执行cout语句再加一"<<endl;
  cout<<j<<endl;
  cout<<++j<<endl;
  cout<<j<<endl;
  
  return 0;
}
